package com.apkcore.bl;

/**
 * 1143. 最长公共子序列Copy for Markdown
 * 给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
 * <p>
 * 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
 * <p>
 * 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
 * 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
 * <p>
 * 示例 1：
 * <p>
 * 输入：text1 = "abcde", text2 = "ace"
 * 输出：3
 * 解释：最长公共子序列是 "ace" ，它的长度为 3 。
 * 示例 2：
 * <p>
 * 输入：text1 = "abc", text2 = "abc"
 * 输出：3
 * 解释：最长公共子序列是 "abc" ，它的长度为 3 。
 * 示例 3：
 * <p>
 * 输入：text1 = "abc", text2 = "def"
 * 输出：0
 * 解释：两个字符串没有公共子序列，返回 0 。
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= text1.length, text2.length <= 1000
 * text1 和 text2 仅由小写英文字符组成。
 * https://leetcode-cn.com/problems/longest-common-subsequence/
 */
public class _1143最长公共子序列 {
    public static void main(String[] args) {
        String text1 = "abcdeccc", text2 = "aececabbadvsdfsdg";
        System.out.println(new _1143最长公共子序列().longestCommonSubsequence3(text1, text2));
    }

    /***
     * 在方法2的基础上进一步优化，考虑是否可以用一维数组来取值
     * 中间态求dp[j]时，可以知道，dp[j-1]已经是新的值left了，而dp[j]还是原表中上面的值top，所以只需要保存一个leftTop值即可
     */
    public int longestCommonSubsequence3(String text1, String text2) {
        if (text1 == null || text1.isEmpty() || text2 == null || text2.isEmpty()) {
            return 0;
        }
        // 设dp[i][j]表示第i个char1和第j个char2有多少个共同子序列
        // 初始值dp[0][j] = 0; dp[i][0] = 0;
        // 状态转移方程：if(char1[i-1]==char1[j-1]) dp[i][j] = dp[i-1][j-1]+1;
        // 不相等时，Math.max(dp[i-1][j],dp[i][j-1]);
        char[] char1 = text1.toCharArray();
        char[] char2 = text2.toCharArray();
        if (char1.length < char2.length) {
            char[] temp = char1;
            char1 = char2;
            char2 = temp;
        }
        int[] dp = new int[char2.length + 1];

        for (int i = 1; i <= char1.length; i++) {
            int cur = 0;
            for (int j = 1; j <= char2.length; j++) {
                int leftTop = cur;
                cur = dp[j];
                if (char1[i - 1] == char2[j - 1]) {
                    dp[j] = leftTop + 1;
                } else {
                    dp[j] = Math.max(dp[j], dp[j - 1]);
                }
            }
        }
        return dp[char2.length];
    }

    /**
     * 画表，可知，我们其实只需要上下两行数据，所以可以使用滚动数组，通过%2来取是哪一行
     */
    public int longestCommonSubsequence2(String text1, String text2) {
        if (text1 == null || text1.isEmpty() || text2 == null || text2.isEmpty()) {
            return 0;
        }
        // 设dp[i][j]表示第i个char1和第j个char2有多少个共同子序列
        // 初始值dp[0][j] = 0; dp[i][0] = 0;
        // 状态转移方程：if(char1[i-1]==char1[j-1]) dp[i][j] = dp[i-1][j-1]+1;
        // 不相等时，Math.max(dp[i-1][j],dp[i][j-1]);
        char[] char1 = text1.toCharArray();
        char[] char2 = text2.toCharArray();
        if (char1.length < char2.length) {
            char[] temp = char1;
            char1 = char2;
            char2 = temp;
        }

        int[][] dp = new int[2][char2.length + 1];

        for (int i = 1; i <= char1.length; i++) {
            // %2可以用&1代替，/2可以用>>1
            int row = i & 1;
            int preRow = (i - 1) & 1;
            for (int j = 1; j <= char2.length; j++) {
                if (char1[i - 1] == char2[j - 1]) {
                    dp[row][j] = dp[preRow][j - 1] + 1;
                } else {
                    dp[row][j] = Math.max(dp[preRow][j], dp[row][j - 1]);
                }
            }
        }
        return dp[char1.length & 1][char2.length];
    }

    public int longestCommonSubsequence1(String text1, String text2) {
        if (text1 == null || text1.isEmpty() || text2 == null || text2.isEmpty()) {
            return 0;
        }
        // 设dp[i][j]表示第i个char1和第j个char2有多少个共同子序列
        // 初始值dp[0][j] = 0; dp[i][0] = 0;
        // 状态转移方程：if(char1[i-1]==char1[j-1]) dp[i][j] = dp[i-1][j-1]+1;
        // 不相等时，Math.max(dp[i-1][j],dp[i][j-1]);
        char[] char1 = text1.toCharArray();
        char[] char2 = text2.toCharArray();
        int[][] dp = new int[char1.length + 1][char2.length + 1];

        for (int i = 1; i <= char1.length; i++) {
            for (int j = 1; j <= char2.length; j++) {
                if (char1[i - 1] == char2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        return dp[char1.length][char2.length];
    }
}
